Thực đơn
Cây van Emde Boas Phương thức hoạt độngCho đơn giản, giả sử log2 m = k với k là số tự nhiên. Giả sử M=2m. Một cây vEB T cho tập hợp {0,..., M-1} có nút gốc chứa 1 mảng mang tên T.con có kích thước M1/2. T.con[i] là con trỏ đến cây vEB con lưu trữ các giá trị trong khoảng {iM1/2,...,(i+1)M1/2-1}. Ngoài ra T chứa hai giá trị T.min và T.max cùng với một cây vEB hỗ trợ T.aux.
Dữ liệu trong cây vEB được lưu trữ như sau. Giá trị nhỏ nhất được lưu trong T.min và giá trị lớn nhất được lưu trong T.max. Hai giá trị này không được lưu tại bất kì nơi nào khác trong cây. Nếu T là rỗng, ta quy ước T.max=-1 và T.min=M. Các giá trị còn lại được lưu trong các cây con. Giá trị x được lưu trong cây con T.con[i] trong đó i = ⌊ x / M 1 / 2 ⌋ {\displaystyle i=\lfloor x/M^{1/2}\rfloor } . Cây hỗ trợ T.aux lưu trữ các cây con khác rỗng. Nghĩa là T.aux chứa giá trị j khi và chỉ khi T.con[j] là khác rỗng.
Thực đơn
Cây van Emde Boas Phương thức hoạt độngLiên quan
Cây Cây sáo thần Cây họ đậu Cây trồng biến đổi gen Cây cứt lợn Cây táo nở hoa Cây gạo Cây lương thực Cây tìm kiếm nhị phân Cây sự sốngTài liệu tham khảo
WikiPedia: Cây van Emde Boas http://www.daimi.au.dk/~gudmund/dynamicF04/vEB.pdf http://theory.csail.mit.edu/classes/6.897/spring03... http://theory.csail.mit.edu/classes/6.897/spring03...